﻿/*
题目：车队

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。

给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并与前车 以相同的速度 紧接着行驶。此时，我们会忽略这两辆车之间的距离，也就是说，它们被假定处于相同的位置。

车队 是一些由行驶在相同位置、具有相同速度的车组成的非空集合。注意，一辆车也可以是一个车队。

即便一辆车在目的地才赶上了一个车队，它们仍然会被视作是同一个车队。

返回到达目的地的 车队数量 。

https://leetcode.cn/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    int carFleet(int target, vector<int>& position, vector<int>& speed) {
        list<pair<int, int>> lst;
        for (int i = 0; i < position.size(); i++) {
            lst.push_back({ position[i], speed[i] });
        }

        // 根据当前距离进行排序
        lst.sort([](pair<int, int>& x, pair<int, int>& y) {
            return x.first < y.first;
            });

        int num = 0;
        while (!lst.empty()) {
            auto it = lst.begin();
            while (it != lst.end()) {
                it->first += it->second;
                if (it == lst.begin()) {
                    ++it;
                    continue;
                }

                auto prev = std::prev(it);
                // 如果被前面的车超过，那么直接拦截，前面的车无法越过前面的车
                while (prev->first >= it->first) {
                    lst.erase(prev);
                    if (it != lst.begin())  prev = std::prev(it);
                    else                    break;
                }
                ++it;
            }

            while (!lst.empty() && lst.back().first >= target) {
                lst.pop_back();
                num++;
            }
        }

        return num;
    }
};

int main() {
    auto p = vector<int>( { 5,26,18,25,29,21,22,12,19,6 });
    auto s = vector<int>( { 7,6,6,4,3,4,9,7,6,4 });
    Solution().carFleet(31, p, s);
    return 0;
}